﻿#pragma once
#include<vector>
#include<iostream>
using namespace std;
// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv) {
			if (Find(kv.first))return false;
			size_t size = _tables.size();
			Hash hf;
			if ((double)_n / size >= 0.7) {
				HashTable<K, V, Hash> newtables;
				size *= 2;
				newtables._tables.resize(size);
				for (int i = 0; i < _tables.size(); i++) {
					newtables.Insert(_tables[i]._kv);
				}
				_tables.swap(newtables._tables);
			}
			size_t hashi = hf(kv.first) % size;
			while (_tables[hashi]._state == EXIST)hashi = (hashi + 1) % size;
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		HashData<K, V>* Find(const K& key) {
			Hash hf;
			size_t size = _tables.size();
			size_t hashi = hf(key) % size;
			while (_tables[hashi]._state != EMPTY) {
				if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)return &_tables[hashi];
				hashi = (hashi + 1) % size;
			}
			return nullptr;
		}
		bool Erase(const K& key) {
			HashData<K, V>* f = Find(key);
			if (f) {
				f->_state = DELETE;
				return true;
			}
			else return false;
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}
